package alogrithm.solution;

/*
 * Stack which implements min() in O(1)
 */
public class P2 {
	private int size=0;
	private int capacity=10;
	private int[] elements;
	private int top=-1;
	private int min[];
	
	public P2()
	{
		elements=new int[capacity];
		min=new int[capacity];
	}
	
	public int size()
	{
		return size;
	}
	public int capacity()
	{
		return capacity;
	}
	public void push(int ele)
	{
		if(size==capacity)
		{
			capacity*=2;
			int temp[]=new int[capacity];
			for(int i=0;i<size;i++)
				temp[i]=elements[i];
			elements=temp;
			temp=new int[capacity];
			for(int i=0;i<size;i++)
				temp[i]=min[i];
			min=temp;
		}
		size++;
		int minElement=ele;
		if(top!=-1)
			minElement=minElement<min[top]?minElement:min[top];
		min[top+1]=minElement;
		elements[top+1]=ele;
		top++;
	}
	
	public int pop() throws Exception
	{
		if(size==0)
		{
			System.err.println("Stack is Empty!");
			throw new Exception();
		}
		else
		{
			int peek=elements[top];
			top--;
			size--;
			if(size<=capacity/2)
			{
				capacity=capacity/2;
				int temp[]=new int[capacity];
				for(int i=0;i<size;i++)
					temp[i]=elements[i];
				elements=temp;
				temp=new int[capacity];
				for(int i=0;i<size;i++)
					temp[i]=min[i];
				min=temp;
			}
			return peek;
		}
	}
	
	public int min() throws Exception
	{
		if(top==-1)
			throw new Exception();
		return min[top];
	}

	/**
	 * @param args
	 * @throws Exception 
	 */
	public static void main(String[] args) throws Exception {
		// TODO Auto-generated method stub
		P2 s=new P2();
		try
		{
			System.out.println(s.min());
		}
		catch(Exception e)
		{
			System.out.println(e);
		}
		s.push(2);
		System.out.println("min:"+s.min()+" size:"+s.size()+" capacity:"+s.capacity());
		s.push(1);
		System.out.println("min:"+s.min()+" size:"+s.size()+" capacity:"+s.capacity());
		s.push(3);
		System.out.println("min:"+s.min()+" size:"+s.size()+" capacity:"+s.capacity());
		s.pop();
		System.out.println("min:"+s.min()+" size:"+s.size()+" capacity:"+s.capacity());
		s.pop();
		System.out.println("min:"+s.min()+" size:"+s.size()+" capacity:"+s.capacity());
		s.push(0);
		System.out.println("min:"+s.min()+" size:"+s.size()+" capacity:"+s.capacity());
		s.push(-100);
		System.out.println("min:"+s.min()+" size:"+s.size()+" capacity:"+s.capacity());
		s.push(-10);
		System.out.println("min:"+s.min()+" size:"+s.size()+" capacity:"+s.capacity());
		s.push(-1000);
		System.out.println("min:"+s.min()+" size:"+s.size()+" capacity:"+s.capacity());

	}

}
